Shortest path in binary matrix

Time: O(N^2); Space: O(N); medium

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, …, C_k such that: * Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner) * C_1 is at location (0, 0) (ie. has value grid[0][0]) * C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1]) * If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

Example 1:

Input: grid = [[0,1],[1,0]]

Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Notes:

  • 1 <= len(grid) == len(grid[0]) <= 100

  • grid[r][c] is 0 or 1

Hint:

  1. Do a breadth first search to find the shortest path.

[3]:

import collections

class Solution1(object):
    """
    Time:  O(n^2)
    Space: O(n)
    """
    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [(-1, -1), (-1, 0), (-1, 1), \
                      ( 0, -1), ( 0, 1), \
                      ( 1, -1), ( 1, 0), ( 1, 1)]
        result = 0
        q = collections.deque([(0, 0)])
        while q:
            result += 1
            next_depth = collections.deque()
            while q:
                i, j = q.popleft()
                if 0 <= i < len(grid) and \
                   0 <= j < len(grid[0]) and \
                    not grid[i][j]:
                    grid[i][j] = 1
                    if i == len(grid)-1 and j == len(grid)-1:
                        return result
                    for d in directions:
                        next_depth.append((i+d[0], j+d[1]))
            q = next_depth
        return -1

[4]:

s = Solution1()
grid = [[0,1],[1,0]]
assert s.shortestPathBinaryMatrix(grid) == 2
grid = [[0,0,0],[1,1,0],[1,1,0]]
assert s.shortestPathBinaryMatrix(grid) == 4